Cho xâu Fibonacci được định nghĩa đệ quy như sau:

F n := F ( n ) := { b khi  n = 0 ; a khi  n = 1 ; F ( n − 1 ) + F ( n − 2 ) khi  n > 1. {\displaystyle F_{n}:=F(n):={\begin{cases}b&{\mbox{khi }}n=0;\\a&{\mbox{khi }}n=1;\\F(n-1)+F(n-2)&{\mbox{khi }}n>1.\\\end{cases}}} ,

trong đó dấu "+" ký hiệu cho phép ghép hai xâu.

Hãy viết giải thuật (đệ quy hoặc phi đệ quy) tính độ dài xâu.

Hãy cho biết giá trị của chuỗi với n = 7

Dãy các xâu Fibonacci khởi đầu là:

b, a, ab, aba, abaab, abaababa, abaababaabaab, …

Độ dài của mỗi xâu Fibonacci chính là số Fibonacci, và có một xâu Fibonacci tương ứng với mỗi số Fibonacci.

Các xâu Fibonacci cung cấp dữ liệu vào cho các minh dụ cho một vài thuật toán máy tính.